package io.github.handyang.algorithms.graph;

import java.util.Arrays;

public class QuickUnionSearch implements Search {
    private int[] index;
    private int[] size;

    public QuickUnionSearch(int N) {
        index = new int[N];
        for (int i = 0; i < index.length; i++) {
            index[i] = i;
        }

        size = new int[N];
        Arrays.fill(size, 1);
    }

    public int findRoot(int v) {
        int root = v;
        while (index[root] != root) {
            root = index[root];
        }

        return root;
    }

    public void mark(int s, int v) {
        int rootS = findRoot(s);
        int rootV = findRoot(v);
        if (rootS == rootV) return;

        if (size[rootS] > size[rootV]) {
            index[rootV] = rootS;
            size[rootS] += size[rootV];
        } else {
            index[rootS] = rootV;
            size[rootV] += size[rootS];
        }
    }

    @Override
    public boolean marked(int s, int v) {
        return findRoot(s) == findRoot(v);
    }

    @Override
    public int count(int s) {
        return 0;
    }
}
